Optimisation convexe : Approximation des inégalités : Des fonctions indicatrices aux barrières lisses

Imaginez que vous pilotez un algorithme de trading haute fréquence. Votre portefeuille dispose d'une limite stricte de risque. Une contrainte « rigide » agit comme un frein d'urgence : elle arrête tout instantanément dès que la limite est atteinte, pouvant potentiellement faire planter la logique du système. En optimisation convexe, nous préférons un système d'avertissement « doux ». Nous remplaçons le relief abrupt et binaire de la fonction indicatrice par une « barrière » lisse et logarithmique qui pénalise de plus en plus l'objectif à mesure que nous nous rapprochons de la frontière. Cela permet à l'optimiseur de « sentir » la contrainte approcher et d'ajuster sa trajectoire de manière fluide, sans jamais sortir des limites.

Le problème de la non-différentiabilité

Le problème d'optimisation contraint classique est défini par :

$$\text{minimiser } f_0(x) \\ \text{avec } f_i(x) \leq 0, \quad i = 1, \ldots, m \\ Ax = b$$

Nous pourrions théoriquement reformuler cela en utilisant la fonction indicatrice $I_-(u)$ pour intégrer les contraintes dans l'objectif. Toutefois, $I_-(u)$ est un monstre pour le calcul différentiel :

$$I_-(u) = \begin{cases} 0 & u \leq 0 \\ \infty & u > 0 \end{cases}$$

En raison de sa discontinuité et de son gradient infini à la frontière, nous ne pouvons pas calculer le hessien requis pour la méthode de Newton. Nous avons besoin d'un substitut différentiable.

Lissage logarithmique

Le substitut

Nous approximons $I_-(u)$ à l'aide de la fonction :

$$\hat{I}_-(u) = -(1/t) \log(-u), \quad \text{dom } \hat{I}_- = -\mathbf{R}_{++}$$

Ici, $t > 0$ est un paramètre qui détermine la précision de notre approximation. Plus $t$ augmente, plus la barrière ressemble à la fonction indicatrice réelle.

Contrainte d'intérieur

Contrairement aux méthodes des ensembles actifs, cette approche exige que chaque itération $x$ reste strictement admissible ($f_i(x) < 0$). Comme le logarithme est indéfini pour les valeurs non négatives, il crée une « barrière infranchissable » qui maintient la recherche à l'intérieur de l'intérieur de l'ensemble admissible.

🎯 Définition : Méthodes des points intérieurs

Méthodes des points intérieurs : méthodes de résolution des problèmes d'optimisation convexe incluant des contraintes d'inégalité en appliquant la méthode de Newton à une séquence de problèmes avec contraintes d'égalité.

QUESTION 1

Pourquoi ne pouvons-nous pas utiliser directement la fonction indicatrice idéale $I_-(u)$ avec la méthode de Newton ?

Elle est non différentiable à la frontière u=0.

Elle rend la fonction objectif non convexe.

Elle nécessite que le domaine soit restreint aux valeurs positives.

La méthode de Newton ne fonctionne qu'avec des problèmes non contraints.

QUESTION 2

Quel est l'effet de l'augmentation du paramètre $t$ dans l'approximation de la barrière logarithmique ?

Elle rend l'approximation plus lisse et plus plate.

Elle « aiguise » la transition à la frontière, la rendant plus semblable à l'indicateur idéal.

Elle permet à l'optimisation de franchir la région inadmissible.

Elle réduit le problème à une instance de programmation linéaire.

QUESTION 3

Laquelle des propositions suivantes est une exigence obligatoire pour les points $x$ dans une méthode des points intérieurs utilisant des barrières logarithmiques ?

$f_i(x) \ge 0$

$f_i(x) < 0$ pour tout i

$f_i(x) = 0$ pour au moins une contrainte active

Le gradient $\nabla f_0(x)$ doit être nul

QUESTION 4

Dans l'analogie de l'algorithme de trading, comment se comporte la barrière logarithmique lorsque le risque approche la limite ?

Elle applique une pénalité croissant exponentiellement à l'objectif.

Elle ignore le risque jusqu'à ce que la limite soit réellement franchie.

Elle diminue la pénalité afin d'encourager la recherche de la frontière.

Elle arrête immédiatement le système.

QUESTION 5

Quel est l'écart de sous-optimalité pour un point sur le chemin central avec $m$ contraintes et le paramètre $t$ ?

$t/m$

$m/t$

$\log(m/t)$

$1/t^2$